Field of the Invention
The present invention generally relates to communications networks. More particular, the present invention related to systems and method for increased data throughput in communications networks.
Description of the Related Art
A wireless channel is generally understood as a pathway between two communication endpoints. Through a wireless channel, the communication of any number of forms of data may take place. The efficient and effective communication of data is, however, subject to any number of characteristics of a particular wireless channel.
For example, a wireless channel with low throughput would not be recommended for the communication of data related to a high-definition television program. Similarly, the use of a wireless channel with a large amount of available bandwidth may be better utilized in the context of time-sensitive data transfers (e.g., voice communications) rather than the exchange of low priority and low-bandwidth background data queries.
Characteristics of a wireless channel may vary over time. For example, a wireless channel that at one moment has available bandwidth may subsequently be subjected to bottlenecks and dropped data packets thus requiring retransmission of the same. These variances in network characteristics may be a result of, for example, terminal mobility, multipath fading, or interference.
With respect to terminal mobility, a terminal may (while in motion) access wireless services from different locations. The mobility of the terminal requires the network to expend resources related to identifying and locating that terminal. The accessing of the network at different locales over time in conjunction with the need of the network to identify and locate the terminal may affect the quality of a wireless signal in that network.
Multipath fading involves the phenomenon of multipath propagation whereby a radio signal arrives at a receiving station (e.g., an antenna), at different times, via two or more paths. Multipath propagation may be induced by the refracting and reflecting of a wireless signal by various objects in the wireless environment (e.g., walls and metal objects). As a result of multipath propagation, the wireless signal is distorted thereby resulting in a deteriorated communications experience, which may include jitter or ghosting in the case of audio or video content.
Interference, broadly stated, may be mobile or static. In the case of mobile interference, the reception of a signal by a first mobile device (e.g., a wireless terminal) may be impeded or degraded by the transmission of a signal by another mobile device. Static interference is representative of the superposition of white noise (i.e., static) and other disturbing influences on a wireless signal. These influences are inclusive of thermal noise, electronic noise from receiver input circuits, and radiated electromagnetic noise that might be picked up by a receiving station's antenna.
FIG. 1A illustrates how characteristics of a wireless channel may vary over time in light of the aforementioned terminal mobility, multipath fading, and interference. FIG. 1A illustrates a wireless channel 100 where signal quality 110 between an access point (AP) and station are illustrated as a function of time 120. As can be seen from FIG. 1A, signal quality 110 is less at T+1 than at T+2. The signal quality 110 for T+1 and T+2 is less than the signal quality 110 illustrated at T+3, which is nearly equivalent to that of the signal quality 110 exhibited at T+4. Signal quality 110 improves at T+5 while experiencing a significant decrease at T+6.
Further complicating the understanding of wireless channel characteristics (and the optimal use of those channels) is that channel conditions often lack correlation amongst one another in a network of stations. The lack of correlation may be a result of different distances from an AP to a particular station, distances from a station (or the AP) to a particular source of interference, the movement of a mobile terminal or station, as well as varying multipath fading effects. FIG. 1B is exemplary in this regard with respect to illustrating the signal quality 110 between the aforementioned AP and Station A (130) and the AP and Station B (140). As shown in FIG. 1B, there is no immediately recognizable correlation in signal quality vis-a-vis the AP and the differing stations (130/140).
One attempt at managing variances in wireless channel characteristics, especially as they pertain to different stations, has been through the use of a scheduler. Schedulers may be embodied in hardware and/or software components—the latter being executable from memory or a storage device by a corresponding processing device—with respect to providing scheduling policies, rules, procedure, or other criteria in making scheduling decisions. A scheduler may, in light of the aforementioned policies or criteria and a given set of packets, select particular packets for serial transmission over a particular wireless channel.
Different scheduling policies may be used in an attempt to ensure a communications network's ability to provide different quality of service (QOS) guarantees. Policies may include strict priority (SP) where a particular station queue is always allocated bandwidth and/or transmitted before other queues. An alternative policy includes round robin (RR) scheduling, which assigns bandwidth and transmits packets in equal portion, in order, and without priority to a particular station queue.
Weighted round robin (WRR), on the other hand, is a best-effort scheduling discipline (i.e., the network does not provide any guarantees that data is delivered or that a user is given a guaranteed QOS level or priority). Through WRR scheduling, station queues can be assigned a weight—an integer value that might indicate capacity or priority. Station queues with higher weights have their packets transmitted prior to those with lesser weights. All queues are eventually given regular transmission access to a channel albeit it those queues with higher weight will get more transmission access attempts than those with lesser weights.
Yet another scheduling policy is fair queuing (FQ), which allows several packet flows to fairly share link capacity. Fair queuing differs from first-in-first-out (FIFO) (i.e., what comes in first is handled first and what comes in next waits until the first is finished) in that an ill-behaved flow that consists of, for example, large data packets or a large number of packets will punish itself and not other packet flows. In FQ scheduling, in order to decide which packet should be forwarded first, the FQ algorithm estimates a virtual finishing time of all candidate packets (i.e., the packets at the head of all non-empty queues) based on, for example, the arrival time of the packet, the packet size, and the number of queues. The FQ scheduling algorithm or policy then compares the virtual finishing time and selects the minimum one. The packet with the minimum virtual finishing time is transmitted.
A still further scheduling policy is weighted fair queuing (WFQ), which allows different scheduling priorities to be statistically multiplexed. WFQ is a generalization of the aforementioned FQ algorithm where each data flow has a separate FIFO queue. Whereas the aforementioned ill-behaved queue will only punish itself, WFQ allows different sessions to have different service shares. If N data flows currently are active, with weights ω1, ω2 . . . ωN, data flow number i will achieve an average data rate of
      R    ⁢                  ⁢          ω      i            (                  ω        1            ❘                        ω          2                ❘                  …          ❘                      ω            N                                )  An end-to-end delay bound can be guaranteed in WFQ scheduling. By dynamically regulating WFQ weights, this policy can be used to control QOS and achieve a guaranteed data rate.
Typical wireless devices (e.g., an 802.11x compliant device) implement a simple class and/or priority scheduling mechanism with a FIFO queue per each traffic class. An example of such a mechanism 200 is illustrated in FIG. 2. The scheduling mechanism 200 of FIG. 2 illustrates four classes of traffic priority: voice (230), video (240), best-effort (250), and background (260). While the voice, video, best-effort, and background represent the typical four traffic priorities, the actual number of classes may vary in order to accommodate, for example, additional traffic classes and management traffic.
In the scheduling mechanism 200 of FIG. 2, packets are introduced to the wireless device via a network/input interface 210. It should be noted that certain hardware components (e.g. a processor or memory) are not illustrated in that one skilled in the art will appreciate and understand the requisite components to implement the various applications disclosed herein. Packets may be received from another wireless device, a network backbone, a router, or a primary source of content that has been converted into data packets for transmission.
Packets are then routed to the classifier 220. The classifier 220 may identify packets based on application layer data regardless of port. The classifier 220 may alternatively identify packets based on Internet Protocol (IP) address, port numbers, and so on. Packet classification based on multiple fields may be implemented using basic search algorithms, geometric algorithms, heuristic algorithms, or hardware-specific search algorithms. A variety of methodologies for packet classification are generally known in the art.
Once classified by classifier 220, packets are then routed to an appropriate queue: voice, video, best-effort, background (230-260). The priority scheduler 270 then schedules the classified and queued packets. In the priority based queuing and scheduling mechanism 200 of FIG. 2, all packet traffic of a specific class (e.g., voice (230) is subjected to FIFO queuing. Scheduling is done strictly by priority (SP). As such, priority N (e.g., voice (230)) must be empty before priority N+1 (e.g., video (240)) is allowed to transmit. Packets are then transmitted or further routed via the appropriate network/output interface 280.
Problems exist with respect to prior art scheduling methodologies based on priority queuing with per class FIFO. Channel aware scheduling (as discussed in further detail below) may not be implemented in this context. For example, traffic to different stations is interleaved within each FIFO queue. Further, only one packet is available at any given time—the packet at the head of the highest priority queue.
Typical prior art scheduler implementations also blindly retransmit the head end packet from the highest priority active queue until that packet is either successfully acknowledged by the recipient or some maximum number of retransmissions occurs. This blind retransmission causes head-of-line blocking. As a result, poor system performance results and, in many circumstances, clients may become completely impaired.